package org.agle4j.algorithm.array.ordered;

/**
 * 二分法查找
 * 
 * @author hanyx
 */
public class OrderArrayWithBinarySearch {

	private int[] datas;
	private int currentIndex = 0;

	public OrderArrayWithBinarySearch(int index) {
		datas = new int[index];
	}

	public int insert(int data) {
		// 假设是升序
		int index = 0;
		// 1.查找数据data应该存放的位置 index
		for (index = 0; index < currentIndex; index++) {
			if (datas[index] > data) {
				break;
			}
		}
		// 2.把这个位置及其后面数据,向后移动一位
		for (int i = currentIndex; i > index; i--) {
			datas[i] = datas[i - 1];
		}
		// 3.把data存放到应该存放的位置
		datas[index] = data;

		currentIndex++;
		return currentIndex - 1;
	}

	public int searchBinarySearch(int data) {
		int index = -1;
		// 用来表示小的这边的索引
		int lowIndex = 0;
		// 用来表示大的这边的索引
		int highIndex = currentIndex - 1;
		
		while (true) { // 一直循环直到找到
			// 1.找到中间的索引位置
			index = (lowIndex + highIndex)/2;
			// 2.把要查找的数据和中间索引位置的数据进行比较
			if (lowIndex > highIndex) {
				return -1;
			} else if (datas[index] == data) {
				return index;
			} else {
				if (data < datas[index]) {
					highIndex = index - 1;
					System.out.println("highIndex: " + highIndex);
				} else {
					lowIndex = index + 1;
					System.out.println("lowIndex: " + lowIndex);
				}
			}
		}
	}

	public void printDatas() {
		for (int i = 0; i < this.currentIndex; i++) {
			System.out.println(this.datas[i]);
		}
		System.out.println("////////////////////");
	}
}
